

const edges = [
    {
        source: 1,
        target: 3
    },
    {
        source: 3,
        target: 5
    },
    {
        source: 2,
        target: 3
    },
    {
        source: 4,
        target: 1
    },
    {
        source: 1,
        target: 6
    },
    {
        target: 5,
        source: 6
    }
];

function findRedundantConnection(edges) {
    // 使用邻接表存储图的信息
    const graph = new Map();

    // 遍历每一条边
    for (let i = 0; i < edges.length; i++) {
        const edge = edges[i];
        // Each element of edges is a pair [u, v] with u < v
        // const u = edge[0];
        // const v = edge[1];
        const u = edge.source;
        const v = edge.target;

        // 深度优先遍历该图，判断u到v之间是否已经存在了一条路径
        let hasPath = dfs(graph, u, v, []);

        if (hasPath == true) {
            return edge;
        } else {
            // 将该边加入到邻接表中
            if (!graph.has(u)) {
                graph.set(u, []);
            }
            const uArr = graph.get(u);
            uArr.push(v);
            graph.set(u, uArr);

            if (!graph.has(v)) {
                graph.set(v, []);
            }
            const vArr = graph.get(v);
            vArr.push(u);
            graph.set(v, vArr);
        }
    }

    return null;
}

// 深度优先遍历该图，判断start到end之间是否已经存在了一条路径
function dfs(graph, start, end, visited) {
    if (!graph.has(start) || !graph.has(end)) {
        return false;
    }

    if (start == end) {
        return true;
    }

    visited.push(start);

    // 遍历start的所有相邻节点
    const startArr = graph.get(start);
    for (let i = 0; i < startArr.length; i++) {
        const adj = startArr[i];
        if (!visited.includes(adj)) {
            if (dfs(graph, adj, end, visited) == true) {
                return true;
            }
        }
    }

    return false;
}
console.log(findRedundantConnection(edges));
